#include <stdlib.h>
#include <string>
#include <iostream>
#include <vector>

using namespace std;


//vonta o vetor vet concatenando os outros vetores
int monta_vet(int *vet, int *vet1,int n1, int *vet2, int n2)
{
    int i;
   
    for(i=0 ; i< n1; i++)
    {
        vet[i] = vet1[i];
    }
    
    for(int j=0; j< n1+n2; j++)
    {
        
        vet[j+n1] = vet2[j];
    }
    
    return n1+n2;
    
}

//funcao para achar as entradas necessarias para ir de um estado a qualquer outro
int floyd( int ***mmef,int **qtdd_mef, int n)
{
    for(int k=0 ;k<n;k++)
    {
        for(int i =0 ;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if( (qtdd_mef[i][k]>0) && (qtdd_mef[k][j]>0) )
                {
                    if((qtdd_mef[i][j] > qtdd_mef[i][k] + qtdd_mef[k][j] )||(qtdd_mef[i][j]==0))
                    {
                        qtdd_mef[i][j] = monta_vet(mmef[i][j], mmef[i][k],qtdd_mef[i][k],mmef[k][j],qtdd_mef[k][j]);
                    }
                }
            }
        }
    }
    
    return 1;
}

//procura pela proxima aresta a ser testada
int proximo_nao_alterado(int *prox_estado, int *prox_entrada, int **done,int linhas, int colunas, int atual)
{
    (*prox_estado) =-1;
    
    
    //verifica se nao esta no mesmo estado
    for(int j=1; j<= colunas ; j++)
    {
        if( done[atual][j]==-1)
        {
                (*prox_estado) = atual;
                (*prox_entrada) = j;
                return  atual;               
        }
    }

    //verifica em outros estados
    for(int i=0; i< linhas; i++)
    {
        for(int j=1; j<= colunas ; j++)
        {
            if( done[i][j]==-1)
            {
                (*prox_estado) = i;
                (*prox_entrada) = j;
                
                return i;
            }
            
        }
    }
    
    return (*prox_estado);
}


//inicializa uma matriz
template <class T>
T ** inicializa_matriz(int nlinha, int ncoluna, T inicial)
{
    T** mat = (T**) malloc (sizeof(T*)*nlinha);
    
    for(int i=0 ; i< nlinha; i++)
    {
        mat[i] = (T*) malloc (sizeof(T)*ncoluna);
        
        for(int j=0 ; j<ncoluna ; j++)
        {
            mat[i][j] = inicial;
        }
    }
    
    return mat;
}

//inicializa uma matriz
template <class T>
void imprime_mat(T** mat, int nlinha, int ncoluna, string nome)
{
    
    cout<<"Imprimindo matriz "<<nome<<endl;
    
    for(int i=0 ; i< nlinha; i++)
    {        
        for(int j=0 ; j<ncoluna ; j++)
        {
            cout<<mat[i][j]<<" ";
        }
        
        cout<<endl;
    }
    
    cout<<endl;
    
    return ;
}

//inicializa uma matriz de vetores
template <class T>
T*** inicializa_matriz_vetor(int nlinha, int ncoluna,int nelem, T inicial)
{
    T*** mat = (T***) malloc (sizeof(T**)*nlinha);
    
    for(int i=0 ; i< nlinha; i++)
    {
        mat[i] = (T**) malloc (sizeof(T*)*ncoluna);
        
        for(int j=0 ; j<ncoluna ; j++)
        {
            mat[i][j] = (T*) malloc (sizeof(T)*nelem);
            
            for(int k=0 ; k<nelem ; k++)
            {
                mat[i][j][k] = inicial;
            }
        }
    }
    
    return mat;
}

//imprime uma matriz de vetores
template <class T>
void imprime_mat_vet(T*** mat, int nlinha, int ncoluna,int nelem, string nome)
{
    
    cout<<"Imprimindo matriz de vetor "<<nome<<endl;
    
    for(int i=0 ; i< nlinha; i++)
    {        
        for(int j=0 ; j<ncoluna ; j++)
        {
            cout<<" i "<<i<<" j "<<j<<"  ";
            for(int k=0 ; k<nelem ; k++)
            {
                cout<<mat[i][j][k]<<" ";
            }
            cout<<endl;
        }        
        cout<<endl;
    }
    
    cout<<endl;
    
    return ;
}

//imprime um vetor
template <class T>
void imprime_vet(T* vet,int ncoluna, string nome)
{
    
    cout<<"Imprimindo vetor "<<nome<<endl;
   
    for(int k=0 ; k<ncoluna ; k++)
    {
        cout<<vet[k]<<" ";
    }
    cout<<endl;

    
    return ;
}


